package com.example.demo.OtherCoding;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-05-13
 * Time: 9:39
 */
public class Code_deleteNodeBST {
    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            //删除节点既没有左树又没有右树
            //删除节点有左树
            //删除节点有右树
            //删除节点既有左树又有右树
            if (root == null) return null;
            if (root.val == key) {
                //root是删除节点
                if (root.left != null && root.right != null) {
                    TreeNode cur = root.right;
                    while (cur.left != null) {
                        cur = cur.left;
                    }
                    cur.left = root.left;
                    return root.right;
                } else if (root.left == null && root.right == null) {
                    return null;
                } else if (root.left == null) {
                    //没有左树
                    return root.right;
                } else {
                    //没有右树
                    return root.left;
                }
            } else if (root.val > key) {
                root.left = deleteNode(root.left, key);
            } else {
                root.right = deleteNode(root.right, key);
            }
            return root;
        }
    }
}
